package queue.deque;

import queue.deque.Deque;

import java.util.Iterator;

public class LinkedListDeQue<E> implements Deque<E>,Iterable<E>{
    @Override
    public boolean offerFirst(E e) {
        if(isFull()){
            return false;
        }
        Node prev = sentinel;
        Node next = sentinel.next;
        Node added = new Node(prev,e,next);
        prev.next = added;
        next.prev = added;
        return true;
    }

    @Override
    public boolean offerLast(E e) {
        if(isFull()){
            return false;
        }
        Node next = sentinel;
        Node prev = sentinel.prev;
        Node added = new Node(prev,e,next);
        next.prev = added;
        prev.next = added;
        return true;
    }

    @Override
    public E pollFirst() {
        if(isEmpty()){
            return null;
        }
        Node removed = sentinel.next;
        Node next = removed.next;
        sentinel.next = next;
        next.prev = sentinel;
        return removed.val;
    }

    @Override
    public E pollLast() {
        if(isEmpty()){
            return null;
        }
        Node removed = sentinel.prev;
        Node prev = removed.prev;
        prev.next = sentinel;
        sentinel.prev = prev;
        return removed.val;
    }

    @Override
    public E peekFirst() {
        if(isEmpty()){
            return null;
        }
        return sentinel.next.val;
    }

    @Override
    public E peekLast() {
        if(isEmpty()){
            return null;
        }
        return sentinel.prev.val;
    }

    @Override
    public boolean isEmpty() {
        return size ==0;
    }

    @Override
    public boolean isFull() {
        return size == capacity;
    }

    class Node{
        Node prev;
        E val;
        Node next;

        public Node(Node prev, E val, Node next) {
            this.prev = prev;
            this.val = val;
            this.next = next;
        }
    }
    Node sentinel = new Node(null,null,null);
    int size=0;
    int capacity;

    public LinkedListDeQue(int capacity) {
        this.capacity = capacity;
        sentinel.next = sentinel;
        sentinel.prev = sentinel;
    }

    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            Node p = sentinel;
            @Override
            public boolean hasNext() {
                return p!=sentinel;
            }

            @Override
            public E next() {
                E val = p.val;
                p = p.next;
                return val;
            }
        };
    }

}
